class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        # 记录删除最小数量的无效括号的长度
        res_length = -1     
        # 判断括号合法性的栈，用于剪枝
        st = []             
        # 记录答案（因为会重复所以要使用set来存储） 
        ans = set()            
        # 记录回溯路径
        path = []           
        n = len(s)

        def dfs(i: int) -> int:
            if i == len(s):
                if st == []:
                    nonlocal res_length
                    if res_length == -1:
                        # 只有第一次执行到此时才会更新res_length的值
                        res_length = len(path)
                    if len(path) == res_length:
                        ans.add(''.join(path))
                return 
            
            # 剪枝
            if n - i + len(path) < res_length:
                return 

            # 小写字母一定选 与st无关
            if s[i] not in '()':
                path.append(s[i])
                dfs(i + 1)
                path.pop()
            else:
                # 选
                path.append(s[i])   # 记录路径
                if s[i] == '(':
                    st.append(s[i]) # '(' 入栈
                    dfs(i + 1)
                    st.pop()        # 恢复现场
                elif s[i] == ')' and st:
                    last = st.pop() # ')' 出栈
                    dfs(i + 1)
                    st.append(last) # 恢复现场
                path.pop()          # 恢复现场

                # 不选
                dfs(i + 1)
        
        dfs(0)  # 回溯入口
        return list(ans)

